/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * 求数组的子集合：数组元素可能重复 
 * 输入：[1,2,2] 
 * 输出： [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月24日
 */
public class SubSetII {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null) {
            return result;
        }
        Arrays.sort(nums);
        //递归的方法
        List<Integer> path = new ArrayList<>();
        findSubset(nums,0,path,result);
        return result;

    }

    /** 查找子元素
     * @param nums
     * @param start
     * @param path
     * @param result
     * @author towan
     * 2015年5月24日
     */
    private void findSubset(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        if(start>nums.length){
            return;
        }
        //保留任意的中间结果
        List<Integer> clone = new ArrayList<>(path);
        result.add(clone);
        
        for(int i=start;i<nums.length;i++){
            //避免结果重复，只取第一个相同值加入到结果中
            if(i!=start && nums[i]==nums[i-1]){
                continue;
            }
            //加入新元素，并递归调用下一个元素
            path.add(nums[i]);
            findSubset(nums, i+1, path, result);
            //回退
            path.remove(path.size()-1);
        }
    }
    
    public static void main(String[] args) {
        int nums [] = {1,2,2};
        SubSetII subSetII = new SubSetII();
        System.out.println(subSetII.subsetsWithDup(nums));
        
    }
}
